package com.alex.algorithm.easy;

import java.util.HashMap;
import java.util.Map;

public class PatheSumIII {
    public static void main(String[] args) {
        BinaryTreeNode root = new BinaryTreeNode();
        root.setValue(10);

        BinaryTreeNode n1 = new BinaryTreeNode();
        n1.setValue(5);
        root.setLeft(n1);

        BinaryTreeNode n2 = new BinaryTreeNode();
        n2.setValue(-3);
        root.setRight(n2);

        BinaryTreeNode n3 = new BinaryTreeNode();
        n3.setValue(11);

        n2.setRight(n3);

        BinaryTreeNode n4 = new BinaryTreeNode();
        n4.setValue(2);
        n1.setRight(n4);

        BinaryTreeNode n5 = new BinaryTreeNode();
        n5.setValue(3);
        n1.setLeft(n5);

        BinaryTreeNode n6 = new BinaryTreeNode();
        n6.setValue(3);
        n5.setLeft(n6);

        BinaryTreeNode n7 = new BinaryTreeNode();
        n7.setValue(-2);
        n5.setRight(n7);

        BinaryTreeNode n8 = new BinaryTreeNode();
        n8.setValue(1);
        n4.setRight(n8);

        output(root);
        System.out.println("-----");
        System.out.println(pathSum(root, 0, 8, new HashMap<>()));
    }

    private static void output(BinaryTreeNode node) {
        if (node != null) System.out.println(node.getValue());
        if (node.getLeft() != null) output(node.getLeft());
        if (node.getRight() != null) output(node.getRight());
    }

    private static int pathSum(BinaryTreeNode root, int count, int target, Map<Integer, Integer>
                        sumCountMap) {
        if (root == null) return 0;
        int curCount = 0;
        count += root.getValue();
        if (count == target) curCount++;
        if (sumCountMap.containsKey(count - target)) {
            curCount += sumCountMap.get(count - target);
        }
        if (sumCountMap.containsKey(count)) {
            sumCountMap.put(count, sumCountMap.get(count) + 1);
        }else {
            sumCountMap.put(count, 1);
        }
        int res = curCount + pathSum(root.getLeft(), count, target, sumCountMap)
                + pathSum(root.getRight(), count, target, sumCountMap);
        sumCountMap.put(count, sumCountMap.get(count) - 1);
        return res;
    }
}
